﻿#define _CRT_SECURE_NO_WARNINGS


//1..输入两个链表，找出它们的第一个公共结点
typedef struct ListNode ListNode;

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {

    ListNode* pcurA = headA;

    ListNode* pcurB = headB;


    int sizeA = 0;

    int sizeB = 0;

    while (pcurA) {

        sizeA++;

        pcurA = pcurA->next;

    }


    while (pcurB)

    {

        sizeB++;

        pcurB = pcurB->next;

    }

    int gap = abs(sizeA - sizeB);


    ListNode* longList = headA;

    ListNode* shortList = headB;


    if (sizeA < sizeB)

    {

        longList = headB;

        shortList = headA;

    }

    while (gap--)

    {

        longList = longList->next;

    }

    while (longList && shortList)

    {

        if (longList == shortList)

        {

            return longList;

        }

        longList = longList->next;

        shortList = shortList->next;

    }

    return NULL;

}



//2.给定一个链表，判断链表中是否有环
typedef struct ListNode ListNode;

bool hasCycle(struct ListNode* head) {


    //使用快慢指针

    ListNode* slow = head;

    ListNode* fast = head;


    while (fast && fast->next)

    {

        slow = slow->next;

        fast = fast->next->next;

        if (slow == fast)

        {

            return true;

        }

    }

    return false;

}



//3.给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL
typedef struct ListNode ListNode;

struct ListNode* detectCycle(struct ListNode* head) {

    ListNode* slow = head;

    ListNode* fast = head;


    while (fast && fast->next)

    {

        slow = slow->next;

        fast = fast->next->next;

        //找相遇点

        if (fast == slow)

        {

            ListNode* pcur = head;

            while (pcur != slow)

            {

                pcur = pcur->next;

                slow = slow->next;

            }

            return pcur;

        }

    }

    return NULL;

}



﻿﻿typedef struct Node Node;


Node* BuyNode(int x)

{

    Node* newnode = (Node*)malloc(sizeof(Node));

    if (newnode == NULL)

    {

        perror("malloc fail!");

    }

    else

    {

        newnode->val = x;

        newnode->next = newnode->random = NULL;

    }

    return newnode;

}

void AddNode(Node* head)

{

    Node* pcur = head;

    while (pcur)

    {

        Node* Next = pcur->next;//保存下一个结点

        Node* newnode = BuyNode(pcur->val);

        pcur->next = newnode;

        newnode->next = Next;


        pcur = Next;

    }

}

struct Node* copyRandomList(struct Node* head) {

    if (head == NULL)

    {

        return NULL;

    }

    //复制链表

    AddNode(head);

    //置random指针

    Node* pcur = head;

    while (pcur)

    {

        Node* copy = pcur->next;

        if (pcur->random != NULL)

        {

            copy->random = pcur->random->next;

        }

        pcur = copy->next;

    }

    //断开链表

    pcur = head;

    Node* newHead, * newTail;

    newHead = newTail = pcur->next;

    while (pcur->next->next)

    {

        pcur = pcur->next->next;

        newTail->next = pcur->next;

        newTail = newTail->next;

    }

    return newHead;

}